package solution1.demo.demo3;


import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    //1.二叉搜索树搜索
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val > val) {
                cur = cur.left;
            } else if(cur.val < val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

//    //2.验证二叉搜索树(dfs)
//    private void dfs(TreeNode root) {
//        if(!flag) {
//            return;
//        }
//        if(root == null) {
//            return;
//        }
//        dfs(root.left);
//        if(!start) {
//            prev = root.val;
//            start = true;
//        } else {
//            if(prev >= root.val) {
//                flag = false;
//            }
//            prev = root.val;
//        }
//        dfs(root.right);
//    }
//
//    private boolean start;
//    private boolean flag = true;
//    private int prev;//上一个结点的值
//    public boolean isValidBST(TreeNode root) {
//        dfs(root);
//        return flag;
//    }

//    //3.二叉搜索树的最小绝对差(dfs)
//    private void dfs(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        dfs(root.left);
//        if(!start) {
//            start = true;
//            prev = root.val;
//        } else {
//            int ans = Math.abs(root.val - prev);
//            if(ans < min) {
//                min = ans;
//            }
//            prev = root.val;
//        }
//        dfs(root.right);
//    }
//
//    private int prev;//上一个结点值
//    private boolean start;//是否第一次
//    private int min = Integer.MAX_VALUE;//最小绝对差
//    public int getMinimumDifference(TreeNode root) {
//        dfs(root);
//        return min;
//    }

    //4.二叉搜索树中的众数(dfs)
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        if(!start) {
            list.add(root.val);
            start = true;
            prev = root.val;
        } else {
            if(prev == root.val) {
                curLength++;
            } else {
                curLength = 0;
            }
            if(curLength > maxLength) {
                list.clear();
                list.add(root.val);
                maxLength = curLength;
            } else if(curLength == maxLength) {
                list.add(root.val);
            }
            prev = root.val;
        }
        dfs(root.right);
    }

    private List<Integer> list = new ArrayList<>();
    private int prev;//上一个结点
    private boolean start;
    private int maxLength;//最大长度
    private int curLength;//当前长度
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

//    //5.二叉树的最近公共祖先(dfs)
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null || root == q || root == p) {
//            return root;
//        }
//        TreeNode left = lowestCommonAncestor(root.left, p, q);
//        TreeNode right = lowestCommonAncestor(root.right, p, q);
//        if(left == null && right == null) {
//            return null;
//        } else if(left != null && right == null) {
//            return left;
//        } else if(left == null && right != null) {
//            return right;
//        } else {
//            return root;
//        }
//    }

    //6.二叉搜索树的最近公共祖先(dfs)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val > Math.max(p.val, q.val)) {
                cur = cur.left;
            } else if(cur.val < Math.min(p.val, q.val)) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    //7.二叉搜索树中的插入操作
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            return node;
        }
        TreeNode prev = null;
        TreeNode cur = root;
        while(cur != null) {
            prev = cur;
            if(cur.val > val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        if(prev.val > val) {
            prev.left = node;
        } else {
            prev.right = node;
        }
        return root;
    }

    //8.修剪二叉搜索树(dfs)
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) {
            return root;
        }
        if(root.val < low) {
            TreeNode node = trimBST(root.right, low, high);
            return node;
        }
        if(root.val > high) {
            TreeNode node = trimBST(root.left, low, high);
            return node;
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

    //9.将有序数组转换为二叉搜索树(dfs)
    private TreeNode createTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        int mid = (right + left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = createTree(nums, left, mid - 1);
        root.right = createTree(nums, mid + 1, right);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return createTree(nums, 0, nums.length - 1);
    }

    //10.把二叉搜索树转化为累加树(dfs)
//    private void dfs(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        dfs(root.right);
//        root.val += prev.val;
//        prev = root;
//        dfs(root.left);
//    }
//
//    private TreeNode prev = new TreeNode(0);
//    public TreeNode convertBST(TreeNode root) {
//        dfs(root);
//        return root;
//    }

}

class Main {
    public static void main(String[] args) {
        TreeNode t0 = new TreeNode(0);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t2 = new TreeNode(2);
        TreeNode t1 = new TreeNode(1);

        t3.left = t0;
        t3.right = t4;
        t0.right = t2;
        t2.left = t1;

        Solution solution = new Solution();
        solution.trimBST(t3, 1, 3);
    }
}
